package Tree;

import java.util.ArrayList;
import java.util.List;

public class _113_PathSumII {
    List<List<Integer>> res = new ArrayList<>();
    int total;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root == null) return res;
        this.total = sum;
        DFS(root,0, new ArrayList<>());
        return res;
    }

    public void DFS(TreeNode root,int sum,List<Integer> list) {
        if (root != null) {
            if (root.left == null && root.right == null) {
                if (sum + root.val == total) {
                    list.add(root.val);
                    res.add(list);
                }
            } else {
                if (root.left != null) {
                    List<Integer> temp = new ArrayList<>(list);
                    temp.add(root.val);
                    DFS(root.left, sum + root.val,temp);
                }
                if (root.right != null) {
                    List<Integer> temp = new ArrayList<>(list);
                    temp.add(root.val);
                    DFS(root.right, sum + root.val,temp);
                }
            }
        }
    }
}
